package lesson9;

import java.util.Scanner;

public class homeworkGuide {

	public static void main(String[] args) {
		
		
		/*
		 * the code below is a simple implementation using O(N) complexity.
		 * The reason of this complexity is the iteration when calculating
		 * the sum. Iterations depend on the number of initial stores.
		 * 
		 * In order to achieve O(logN) we have to use HEAP construction.
		 * We can save the sums of particular ranges of stores in each
		 * node of the heap.
		 * 
		 * Try this:
		 * Construct a max heap that has a bottom level of all stores and 
		 * their sales. Each upper level of the heap can store the sum
		 * of its children. The root of the heap will then store the sum
		 * of all sales in all stores.
		 * 
		 * When prompted to calculate sum of particular range of stores, 
		 * for example from 3 to 6, try to represent this summation as 
		 * sum(0,6) - sum(0,3). Then for each of these sums you can iterate
		 * the heap from the root and check which children of the root 
		 * should be added to the sum. The calculation of each sum is logN.
		 * 
		 * 
		 */
		
		
		
		Scanner s = new Scanner(System.in);
		int numberOfStores = 10;
		int[] storePrices = new int[numberOfStores];
		int n = -1;
		while (true)
		{
			System.out.println("Enter operation: 1 for input sale. 2 for checkups. 0 for exit.");
			n = s.nextInt();
			switch(n)
			{
				case 1:
				{
					System.out.println("Enter number of store and sale price");
					int store = s.nextInt();
					int price = s.nextInt();
					storePrices[store]+= price;
					break;
				}
				case 2:
				{
					System.out.println("Enter first and last store for checkup");
					int firstStore = s.nextInt();
					int lastStore = s.nextInt();
					int sum = 0;
					for(int i = firstStore; i <= lastStore; i++)
					{
						sum+= storePrices[i];
					}
					System.out.println("Sum = " + sum);
					break;
				}
				default:
					break;
			}
		}
	}
}
